{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #两数之和 IV - 输入二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数之和 IV - 输入二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉搜索树的 <strong>根节点</strong> <code>root</code>&nbsp;和一个整数 <code>k</code> , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 <code>k</code> 。假设二叉搜索树中节点的值均唯一。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root =<strong> </strong>[8,6,10,5,7,9,11], k = 12\n",
    "<strong>输出: </strong>true\n",
    "<strong>解释: </strong>节点 5 和节点 7 之和等于 12\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root =<strong> </strong>[8,6,10,5,7,9,11], k = 22\n",
    "<strong>输出: </strong>false\n",
    "<strong>解释: </strong>不存在两个节点值之和为 22 的节点\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是&nbsp;&nbsp;<code>[1, 10<sup>4</sup>]</code>.</li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>root</code>&nbsp;为二叉搜索树</li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 653 题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/\">https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [opLdQZ](https://leetcode.cn/problems/opLdQZ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [opLdQZ](https://leetcode.cn/problems/opLdQZ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,6,10,5,7,9,11]\\n12', '[8,6,10,5,7,9,11]\\n22']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def midTravel(root):\n",
    "            stack = []\n",
    "            queue = []\n",
    "            while root or stack:\n",
    "                if root:\n",
    "                    stack.append(root)\n",
    "                    root = root.left\n",
    "                else:\n",
    "                    root = stack.pop()\n",
    "                    queue.append(root.val)\n",
    "                    root = root.right\n",
    "            return queue\n",
    "        queue = midTravel(root)\n",
    "        i, j = 0, len(queue)-1\n",
    "        while i < j:\n",
    "            if queue[i] + queue[j] < k:\n",
    "                i += 1\n",
    "            elif queue[i] + queue[j] > k:\n",
    "                j -= 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        tmp = set()\n",
    "\n",
    "        wait = deque()\n",
    "        wait.append(root)\n",
    "        while wait:\n",
    "            node = wait.popleft()\n",
    "            if k - node.val in tmp: return True\n",
    "            \n",
    "            tmp.add(node.val)\n",
    "            if node.left is not None: wait.append(node.left)\n",
    "            if node.right is not None: wait.append(node.right)\n",
    "        return False\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        s = set()\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if k - node.val in s:\n",
    "                return True\n",
    "            s.add(node.val)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        p = root\n",
    "        st = []\n",
    "        s = 0\n",
    "        num = []\n",
    "        while p or st:\n",
    "            while p:\n",
    "                st.append(p)\n",
    "                p = p.left\n",
    "            p = st.pop()\n",
    "          \n",
    "            num.append(p.val)\n",
    "\n",
    "            p = p.right\n",
    "\n",
    "        i = 0\n",
    "        j = len(num) -1\n",
    "        while i < j :\n",
    "            if num[i] + num[j] == k:\n",
    "                return True\n",
    "            if num[i] + num[j] > k:\n",
    "                j -= 1\n",
    "            if num[i] + num[j] < k:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        s = set()\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if k - node.val in s:\n",
    "                return True\n",
    "            s.add(node.val)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        s = set()\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if k - node.val in s:\n",
    "                return True\n",
    "            s.add(node.val)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        s = set()\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if k - node.val in s :\n",
    "                return True\n",
    "            s.add(node.val)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "        return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        s = set()\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if k - node.val in s:\n",
    "                return True\n",
    "            s.add(node.val)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        out = []\n",
    "        tree = collections.deque()\n",
    "        tree.append(root)\n",
    "        while tree:\n",
    "            tmp = []\n",
    "            for i in range(len(tree)):\n",
    "                node = tree.popleft()\n",
    "                if node.val in out:\n",
    "                    return True\n",
    "                else:\n",
    "                    if k - node.val not in out:\n",
    "                        out.append(k - node.val)\n",
    "                    else:\n",
    "                        pass\n",
    "                if node.left: tree.append(node.left)\n",
    "                if node.right: tree.append(node.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        needs = set() \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return False \n",
    "            if k-root.val in needs:\n",
    "                return True \n",
    "            needs.add(root.val)\n",
    "            return dfs(root.left) or dfs(root.right) \n",
    "        return dfs(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        queue=[root]\n",
    "        hash_table=defaultdict(int)\n",
    "        while queue:\n",
    "            node=queue.pop()\n",
    "            if node.val in hash_table.values():\n",
    "                return True\n",
    "            else:\n",
    "                hash_table[node.val]= k-node.val\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n",
    "\n",
    "        \n",
    "                 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        queue = [root]\n",
    "        res = []\n",
    "\n",
    "        while queue:\n",
    "            for node in queue:\n",
    "                res.append(node.val)\n",
    "            l1 = []\n",
    "            for q in queue:\n",
    "                if q.left:\n",
    "                   l1.append(q.left)\n",
    "                if q.right:\n",
    "                    l1.append(q.right)\n",
    "            queue = l1\n",
    "\n",
    "        find = False\n",
    "        d = {}\n",
    "        for i, num in enumerate(res):\n",
    "            complement = k - num\n",
    "            if complement in d:\n",
    "                find = True\n",
    "            d[num] = i\n",
    "        \n",
    "        return find\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        to_find = set()\n",
    "        to_visit = [root]\n",
    "        while to_visit:\n",
    "            node = to_visit.pop()\n",
    "            if node.val in to_find:\n",
    "                return True\n",
    "            to_find.add(k-node.val)\n",
    "            if node.left:\n",
    "                to_visit.append(node.left)\n",
    "            if node.right:\n",
    "                to_visit.append(node.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.l = set()\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.l:\n",
    "            return True\n",
    "        self.l.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left,k) or self.findTarget(root.right,k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def  __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        \n",
    "        if (k - root.val) in self.s:\n",
    "            return True\n",
    "\n",
    "        self.s.add(root.val)\n",
    "        \n",
    "\n",
    "        return self.findTarget(root.left,k) or self.findTarget(root.right,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.k = k\n",
    "        self.visited = set()\n",
    "        return self.inorder(root)\n",
    "    \n",
    "    def inorder(self, root):\n",
    "        if root.left and self.inorder(root.left):\n",
    "            return True\n",
    "        \n",
    "        if (self.k - root.val) in self.visited:\n",
    "            return True\n",
    "        self.visited.add(root.val)\n",
    "        \n",
    "        if root.right and self.inorder(root.right):\n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        res = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return False\n",
    "            if k - node.val in res:\n",
    "                return True\n",
    "            res.add(node.val)\n",
    "            return dfs(node.left) or dfs(node.right)\n",
    "\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "    \n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root :\n",
    "            return False\n",
    "        if k - root.val in self.s :\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left,k) or self.findTarget(root.right,k)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left,k) or self.findTarget(root.right,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root == None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sub_func(self, node):\n",
    "        if node == None:\n",
    "            return False\n",
    "        flag = False\n",
    "        if (self.k - node.val) in self.s:\n",
    "            return True\n",
    "        else:\n",
    "            self.s.add(node.val)\n",
    "\n",
    "        if self.sub_func(node.left):\n",
    "            return True\n",
    "        if self.sub_func(node.right):\n",
    "            return True\n",
    "\n",
    "        return flag\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        # 将二叉树堆化, 小顶堆\n",
    "        self.s = set()\n",
    "        self.k = k\n",
    "\n",
    "        return self.sub_func(root)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        dic = {}\n",
    "        def search(root):\n",
    "            if root is None:\n",
    "                return False\n",
    "            if k-root.val in dic:\n",
    "                return True\n",
    "            dic[root.val]=0\n",
    "            return search(root.left) or search(root.right)\n",
    "        return search(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# #v1\n",
    "# class Solution:\n",
    "#     def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "#         self.nodes = set()\n",
    "#         def finddfs(root):\n",
    "#             if root:\n",
    "#                 self.nodes.add(root.val)\n",
    "#                 finddfs(root.left)\n",
    "#                 finddfs(root.right)\n",
    "        \n",
    "#         finddfs(root)\n",
    "#         print(self.nodes)\n",
    "#         for i in self.nodes:\n",
    "#             print(i)\n",
    "#             print(k-i)\n",
    "#             if (k - i) in self.nodes and i != (k-i):\n",
    "#                 return True\n",
    "\n",
    "#         return False\n",
    "\n",
    "# v2 \n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nodes = set()\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if (k - root.val) in self.nodes:\n",
    "            return True \n",
    "        self.nodes.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def find(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            if k-root.val in nodes:\n",
    "                return True\n",
    "            nodes.add(root.val)\n",
    "            return find(root.left) or find(root.right)\n",
    "        nodes = set()\n",
    "        return find(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = []\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.append(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            \n",
    "            if k - root.val in dic:\n",
    "                return True\n",
    "            \n",
    "            dic.add(root.val)\n",
    "            return recur(root.left) or recur(root.right)\n",
    "\n",
    "        dic = set()\n",
    "        return recur(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.set = set()\n",
    "        def dfs(node):\n",
    "            if not node: return False\n",
    "            if k - node.val in self.set:\n",
    "                return True\n",
    "            self.set.add(node.val)\n",
    "            if dfs(node.left) or dfs(node.right):\n",
    "                return True\n",
    "            return False\n",
    "        return dfs(root)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "\n",
    "        if k-root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k) \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.d = {}\n",
    "        self.flag = False\n",
    "        def dfs(r):\n",
    "            if r == None:\n",
    "                return\n",
    "            dfs(r.left)\n",
    "            if k-r.val in self.d:\n",
    "                self.flag = True\n",
    "                return\n",
    "            if r.val not in self.d:\n",
    "                self.d[r.val] = 1\n",
    "            dfs(r.right)\n",
    "        dfs(root)\n",
    "        return self.flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        dic = set()\n",
    "        def dfs(rt):\n",
    "            if rt:\n",
    "                if k - rt.val in dic:\n",
    "                    return True\n",
    "                else:\n",
    "                    dic.add(rt.val)\n",
    "                    return dfs(rt.left) or dfs(rt.right)\n",
    "            return False\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def in_order(node):\n",
    "            if node:\n",
    "                yield from in_order(node.left)\n",
    "                yield node.val\n",
    "                yield from in_order(node.right)\n",
    "        \n",
    "        def in_order_reverse(node):\n",
    "            if node:\n",
    "                yield from in_order_reverse(node.right)\n",
    "                yield node.val\n",
    "                yield from in_order_reverse(node.left)\n",
    "\n",
    "        left_gen, right_gen = in_order(root), in_order_reverse(root)\n",
    "        left, right = next(left_gen), next(right_gen)\n",
    "        while left < right:\n",
    "            if (v := left + right) == k:\n",
    "                return True\n",
    "            elif v > k:\n",
    "                right = next(right_gen)\n",
    "            else:\n",
    "                left = next(left_gen)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        flag = set()\n",
    "        def dfs(root):\n",
    "            if not root:return False\n",
    "            if k-root.val in flag:return True\n",
    "            flag.add(root.val)\n",
    "            return dfs(root.left)|dfs(root.right)\n",
    "        return dfs(root)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.lis = []\n",
    "        self.inOrder(root)\n",
    "        for i in range(len(self.lis)-1):\n",
    "            for j in range(i+1,len(self.lis)):\n",
    "                if self.lis[i] + self.lis[j] == k:\n",
    "                    return True\n",
    "                elif self.lis[i] + self.lis[j] > k:\n",
    "                    break\n",
    "        return False\n",
    "\n",
    "    def inOrder(self, root):\n",
    "        if root.left:\n",
    "            self.inOrder(root.left)\n",
    "        self.lis.append(root.val)\n",
    "        if root.right:\n",
    "            self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.node_list.append(root.val)\n",
    "        self.dfs(root.left)\n",
    "        self.dfs(root.right)\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.node_list = []\n",
    "        self.dfs(root)\n",
    "        for i in self.node_list:\n",
    "            if k - i in self.node_list and k != 2*i:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root is None: return False\n",
    "        self.nodes = []\n",
    "        def inorder(root):\n",
    "            if root:\n",
    "                inorder(root.left)\n",
    "                self.nodes.append(root.val)\n",
    "                inorder(root.right)\n",
    "        inorder(root)\n",
    "        i, j = 0, len(self.nodes)-1\n",
    "        while i<j:\n",
    "            if self.nodes[i]+self.nodes[j]==k:\n",
    "                return True\n",
    "            elif self.nodes[i]+self.nodes[j]<k:\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s =set()\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        \n",
    "        if k -root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left,k) or self.findTarget(root.right,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set () \n",
    "        \n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k-root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.rs=set()\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k-root.val in self.rs:\n",
    "            return True\n",
    "        self.rs.add(root.val)\n",
    "        return self.findTarget(root.left,k) or self.findTarget(root.right,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.hashmap=dict()\n",
    "        return self.search(root, k)\n",
    "    \n",
    "    def search(self, node, k):\n",
    "        if not node:\n",
    "            return False\n",
    "        if k-node.val in self.hashmap:\n",
    "            return True\n",
    "        self.hashmap[node.val]=1\n",
    "        left=self.search(node.left, k)\n",
    "        if left:\n",
    "            return left\n",
    "        right=self.search(node.right, k)\n",
    "        if right:\n",
    "            return right\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.hash = set()\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root==None:\n",
    "            return False\n",
    "        elif k-root.val in self.hash:\n",
    "            return True\n",
    "        self.hash.add(root.val) \n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def dfs(node, k):\n",
    "            if not node:\n",
    "                return False\n",
    "            if k - node.val in vis:\n",
    "                return True\n",
    "            vis.add(node.val)\n",
    "            return dfs(node.left, k) or dfs(node.right, k)\n",
    "\n",
    "        vis = set()\n",
    "        return dfs(root, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.hashset=set()\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val in self.hashset:\n",
    "            return True\n",
    "        self.hashset.add(k-root.val)\n",
    "        return self.findTarget(root.left,k) or self.findTarget(root.right,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "\n",
    "        self.out = False\n",
    "        self.k = k\n",
    "\n",
    "        self.hsh = {}\n",
    "\n",
    "        self.tr_(root)\n",
    "\n",
    "        return self.out\n",
    "\n",
    "        \n",
    "    def tr_(self, root):\n",
    "\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        if self.out:\n",
    "            return None\n",
    "        \n",
    "        rv = root.val\n",
    "\n",
    "        \n",
    "\n",
    "        tg = self.k - rv\n",
    "\n",
    "        if tg in self.hsh:\n",
    "            self.out = True\n",
    "        else:\n",
    "            self.hsh[rv] = True\n",
    "            self.tr_(root.left)\n",
    "            self.tr_(root.right)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        exist=set()\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            if k-root.val in exist:\n",
    "                return True\n",
    "            else:\n",
    "                exist.add(root.val)\n",
    "            if traverse(root.left):\n",
    "                return True\n",
    "            if traverse(root.right):\n",
    "                return True\n",
    "        return True if traverse(root) else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            \n",
    "            if k - root.val in dic:\n",
    "                return True\n",
    "            \n",
    "            dic.add(root.val)\n",
    "            return recur(root.right) or recur(root.left)\n",
    "\n",
    "        dic = set()\n",
    "        return recur(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        mp = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "\n",
    "            r = k - node.val\n",
    "            if r in mp:\n",
    "                return True\n",
    "\n",
    "            mp.add(node.val)\n",
    "            \n",
    "            return dfs(node.left) or dfs(node.right)\n",
    "        \n",
    "        return dfs(root)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        ex = set()\n",
    "        def dfs(node, k):\n",
    "            if node:\n",
    "                t = k - node.val\n",
    "                if t in ex:\n",
    "                    return True\n",
    "                else:\n",
    "                    ex.add(node.val)\n",
    "                return dfs(node.left, k) or dfs(node.right, k)\n",
    "            return False\n",
    "                \n",
    "        return dfs(root, k)\n",
    "    \n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        vis = set()\n",
    "        flag = False\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal flag\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if k - root.val in vis:\n",
    "                flag = True\n",
    "                return\n",
    "            vis.add(root.val)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.dic = dict()\n",
    "        self.res = False\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if root.val in self.dic:\n",
    "                self.res = True\n",
    "                return\n",
    "            self.dic[k-root.val] = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        d = set()\n",
    "        def recurse(root):\n",
    "            nonlocal d\n",
    "            if root == None:\n",
    "                return False\n",
    "            if k - root.val in d:\n",
    "                return True\n",
    "            else:\n",
    "                d.add(root.val)\n",
    "            res = False\n",
    "            res |= recurse(root.left)\n",
    "            res |= recurse(root.right)\n",
    "            return res\n",
    "        return recurse(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            nonlocal d \n",
    "            v = root.val \n",
    "            if k - v in d:\n",
    "                nonlocal flag\n",
    "                flag = True\n",
    "                return \n",
    "            d.add(v)\n",
    "            dfs(root.right)\n",
    "        flag = False \n",
    "        d = set()\n",
    "        dfs(root)\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        #遍历二叉树，将结点值放入哈希表，\n",
    "        mp = defaultdict(int)\n",
    "        def inOrder(root: TreeNode):\n",
    "            if root is None: return \n",
    "            inOrder(root.left)\n",
    "            mp[root.val] += 1\n",
    "            inOrder(root.right)\n",
    "\n",
    "        inOrder(root)\n",
    "        print(mp)\n",
    "        for key, value in mp.items():\n",
    "            left = k - key\n",
    "            if left == key and mp[left] > 1: return True\n",
    "            if left != key and left in mp: return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        myset = set()\n",
    "        def dfs(node):\n",
    "            if node.val in myset:\n",
    "                return True\n",
    "            else:\n",
    "                myset.add(k-node.val)\n",
    "                ans1 = False\n",
    "                ans2 = False\n",
    "            if node.left:\n",
    "                ans1 = dfs(node.left)\n",
    "            if node.right:\n",
    "                ans2 = dfs(node.right)\n",
    "            return ans1 or ans2 or False\n",
    "\n",
    "        return (dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def query(self, root, val):\n",
    "        if root is None: return None\n",
    "        if val < root.val: return self.query(root.left, val)\n",
    "        elif val > root.val: return self.query(root.right, val)\n",
    "        else: return root\n",
    "\n",
    "    def dfs(self, node, k, root):\n",
    "        if node is None: return False\n",
    "        tgt = k - node.val\n",
    "        if tgt != node.val and self.query(root, tgt):\n",
    "            return True\n",
    "        if self.dfs(node.left, k, root): return True\n",
    "        return self.dfs(node.right, k, root)\n",
    "        \n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        # if root is None: return False\n",
    "        # tgt = k - root.val\n",
    "        # if tgt != root.val and self.query(root, tgt):\n",
    "        #     return True\n",
    "        # if self.findTarget(root.left, k): return True\n",
    "        # return self.findTarget(root.right, k)\n",
    "        return self.dfs(root, k, root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "            \n",
    "        self.nodes = []\n",
    "        self.inorder(root)\n",
    "        \n",
    "        left, right = 0, len(self.nodes) - 1\n",
    "        while left < right:\n",
    "            current_sum = self.nodes[left] + self.nodes[right]\n",
    "            if current_sum < k:\n",
    "                left += 1\n",
    "            elif current_sum > k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "            \n",
    "    def inorder(self, node: TreeNode) -> None:\n",
    "        if not node:\n",
    "            return \n",
    "        self.inorder(node.left)\n",
    "        self.nodes.append(node.val)\n",
    "        self.inorder(node.right)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "\n",
    "        self.arr = []\n",
    "        def check(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            self.arr.append(root.val)\n",
    "            check(root.left)\n",
    "            check(root.right)\n",
    "\n",
    "        print(self.arr)\n",
    "        check(root)\n",
    "\n",
    "        for i in range(len(self.arr)):\n",
    "            for j in range(i+1, len(self.arr)):\n",
    "                if self.arr[i] + self.arr[j] == k:\n",
    "\n",
    "                    return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        res = set()\n",
    "        self.flag = False\n",
    "        def helper(root):\n",
    "            if not root: return None\n",
    "            helper(root.left)\n",
    "            if k - root.val in res:\n",
    "                self.flag = True\n",
    "            res.add(root.val)\n",
    "            helper(root.right)\n",
    "        helper(root)\n",
    "        return self.flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    #定义辅助函数，用于中序遍历\n",
    "    def inorder(self, node: TreeNode) -> None:\n",
    "        #如果节点不存在，返回None（return后面为空说明返回None)\n",
    "        if not node:\n",
    "            return \n",
    "        #遍历左子树\n",
    "        self.inorder(node.left)\n",
    "        #将当前节点的值添加到self.nodes\n",
    "        self.nodes.append(node.val)\n",
    "        #遍历右子树\n",
    "        self.inorder(node.right)\n",
    "    \n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        #如果根节点不存在，返回False\n",
    "        if not root:\n",
    "            return False\n",
    "        \n",
    "        #初始化一个空列表，用于保存中序遍历得到的节点值\n",
    "        self.nodes = []\n",
    "        #对二叉搜索树进行中序遍历\n",
    "        self.inorder(root)\n",
    "        \n",
    "        left, right = 0, len(self.nodes) - 1\n",
    "        while left < right:\n",
    "            current_sum = self.nodes[left] + self.nodes[right]\n",
    "            if current_sum < k:\n",
    "                left += 1\n",
    "            elif current_sum > k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "#本题和两数之和的区别就在于多了个二叉树，核心思想还是一致的           \n",
    "    \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        s = set()\n",
    "        res = False\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:return\n",
    "            if k - root.val in s:\n",
    "                res = True\n",
    "            s.add(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def find(root, val):\n",
    "            if not root: return False\n",
    "            # print(root.val)\n",
    "            if root.val == val: return True\n",
    "            if root.val < val:\n",
    "                return find(root.right, val)\n",
    "            else:\n",
    "                return find(root.left, val)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return False\n",
    "            # print('find:', k-node.val)\n",
    "            if node.val != k-node.val and find(root, k-node.val):\n",
    "                # print(node.val, k-node.val)\n",
    "                return True\n",
    "            \n",
    "            return dfs(node.left) or dfs(node.right)\n",
    "        \n",
    "        return dfs(root)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.flag = 0\n",
    "        self.dic = set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if k - root.val in self.dic:\n",
    "                self.flag = 1\n",
    "            self.dic.add(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        if self.flag == 1:\n",
    "            return True\n",
    "        return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        global head\n",
    "        head = root\n",
    "\n",
    "        def deep_travel(root, k):\n",
    "            \n",
    "            if not root:\n",
    "                return False\n",
    "            print(root.val,k)\n",
    "            if root.val == k:\n",
    "                return True\n",
    "            elif root.val > k:\n",
    "                return deep_travel(root.left,k)\n",
    "            elif root.val <k:\n",
    "                return deep_travel(root.right,k)\n",
    "        \n",
    "        def travel(root):    \n",
    "            global head  \n",
    "            if not root:\n",
    "                return False\n",
    "            print(\"'''''''''''\")\n",
    "            print(root.val)    \n",
    "            if deep_travel(head, k-root.val) == True and k!= 2* root.val:\n",
    "                print(\"bingo\")\n",
    "                return True\n",
    "            else:\n",
    "                return travel(root.left) or travel(root.right)\n",
    "\n",
    "        return travel(root) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        s = set()\n",
    "        res = False\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if root.val in s:\n",
    "                res = True\n",
    "            else:\n",
    "                s.add(k - root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "     def __init__(self, val=0, left=None, right=None):\n",
    "         self.val = val\n",
    "         self.left = left\n",
    "         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def inorder(root):\n",
    "            if root == None:\n",
    "                return []\n",
    "            return inorder(root.left)+[root.val]+inorder(root.right)\n",
    "        nums = inorder(root)\n",
    "        n =len(nums)\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        while left<right:\n",
    "            if nums[left]+nums[right]==k:\n",
    "                return True\n",
    "            if nums[left]+nums[right]<k:\n",
    "                left +=1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            nodes.append(root.val)\n",
    "            dfs(root.right)\n",
    "\n",
    "        nodes = []\n",
    "        dfs(root)\n",
    "        left, right = 0, len(nodes) - 1\n",
    "        while left < right:\n",
    "            if nodes[left] + nodes[right] < k:\n",
    "                left += 1\n",
    "            elif nodes[left] + nodes[right] > k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def inorder_traversal(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)\n",
    "\n",
    "\n",
    "        nums = inorder_traversal(root)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]+nums[j]==k:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.l = []\n",
    "        def f(root):\n",
    "            if not root: return\n",
    "            f(root.left)\n",
    "            self.l.append(root.val)\n",
    "            f(root.right)\n",
    "        f(root)\n",
    "\n",
    "        i, j = 0, len(self.l) - 1\n",
    "        while i <j:\n",
    "            if self.l[i] + self.l[j] == k:\n",
    "                return True\n",
    "            if self.l[i] + self.l[j] > k:\n",
    "                j -= 1\n",
    "            if self.l[i] + self.l[j] < k:\n",
    "                i += 1\n",
    "        return False                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        lis = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            lis.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        i = 0\n",
    "        j = len(lis) - 1\n",
    "        while i < j:\n",
    "            s = lis[i] + lis[j]\n",
    "            if s == k:\n",
    "                return True\n",
    "            if s < k:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return \n",
    "        self.dfs(node.left)\n",
    "        self.nums.append(node.val)\n",
    "        self.dfs(node.right)\n",
    "\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.nums = []\n",
    "        self.dfs(root)\n",
    "        l, r = 0, len(self.nums) - 1\n",
    "        while l < r:\n",
    "            if self.nums[l] + self.nums[r] == k:\n",
    "                return True\n",
    "            if self.nums[l] + self.nums[r] > k:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        arr=[]\n",
    "\n",
    "        def inorder(root):\n",
    "            if root:\n",
    "                inorder(root.left)\n",
    "                arr.append(root.val)\n",
    "                inorder(root.right)\n",
    "        inorder(root)\n",
    "        \n",
    "\n",
    "        l,r=0,len(arr)-1\n",
    "\n",
    "        while l<r:\n",
    "            curr=arr[l]+arr[r]\n",
    "            if curr==k:\n",
    "                return True\n",
    "            elif curr<k:\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
